#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>

using namespace std;
/*
详细思路（含示例说明）
1 边界处理
若原区间列表为空如intervals=[]直接将新区间如newInterval=[2,5]加入结果返回结果为[[2,5]]
2 初始化标记变量
用inserted布尔变量标记新区间是否已插入结果避免重复添加或遗漏
3 遍历原区间列表分四种核心情况处理
  a 当前区间完全在新区间左侧当前区间右端点 < 新区间左端点
    示例intervals=[[1,2],[5,7]] newInterval=[3,6]遍历到[1,2]时满足2<3将[1,2]加入结果继续遍历下一个区间
    操作直接将当前区间加入结果列表i自增进入下一轮循环
  b 新区间左端点在当前区间左侧新区间左端点 < 当前区间左端点
    示例intervals=[[1,5]] newInterval=[0,3]0<1满足此条件
    操作以新区间左端点0作为合并区间左边界继续遍历后续区间这里i=0进入内层循环检查3>=1i自增到1退出内层
    合并右边界取新区间右端点3和最后重叠区间右端点5的最大值5合并区间为[0,5]加入结果标记inserted=true并跳出循环
  c 新区间左端点落在当前区间内当前区间左端点 ≤ 新区间左端点 ≤ 当前区间右端点
    示例intervals=[[1,3],[6,9]] newInterval=[2,5]遍历到[1,3]时2在1-3之间满足此条件
    操作以当前区间左端点1作为合并区间左边界i自增到1检查5>=6不满足退出内层循环
    合并右边界取5和3的最大值5合并区间为[1,5]加入结果标记inserted=true并跳出循环
  d 新区间在当前区间左侧新区间右端点 < 当前区间左端点
    示例intervals=[[4,6]] newInterval=[1,2]2<4满足此条件
    操作直接将新区间[1,2]加入结果标记inserted=true并跳出循环后续区间[4,6]在最后追加
    若不满足此条件如intervals=[[2,3],[5,7]] newInterval=[4,6]遍历到[2,3]时4>3不满足则将当前区间加入结果i自增
4 处理未插入的情况
若遍历结束后inserted仍为false说明新区间在所有区间右侧
示例intervals=[[1,2],[3,5]] newInterval=[6,8]遍历完所有区间后inserted=false直接将[6,8]追加到结果
5 追加剩余区间
将遍历过程中未处理的剩余区间全部加入结果列表
示例intervals=[[1,2],[6,9]] newInterval=[3,5]插入[3,5]后i=2将[6,9]追加到结果最终结果为[[1,2],[3,5],[6,9]]
*/

    class Solution {
    public:
        vector<vector<int>> insert(vector<vector<int>>& intervals,
                                vector<int>& newInterval) {
            vector<vector<int>> ret;
            if (intervals.size() == 0) {
                ret.push_back(newInterval);
                return ret;
            }
            int mid = intervals.size() / 2;
            bool inserted = false; // 标记是否已插入合并区间

            int i = 0;
            while (i < intervals.size()) 
            {
                    // 当前区间完全在newInterval左侧直接插入当前区间，继续遍历
                if(newInterval[0] > intervals[i][1])
                {
                    ret.push_back(intervals[i]);
                    i++;
                }
                // newInterval左端点在当前区间左侧（覆盖当前区间左边界）的情况
                else if(newInterval[0] < intervals[i][0])
                {
                    vector<int> tmp{newInterval[0]};
                    while (i < intervals.size() && newInterval[1] >= intervals[i][0]) 
                    {
                        i++;
                    }
                    int right = (i > 0) ? max(newInterval[1], intervals[i - 1][1]) : newInterval[1];
                    tmp.push_back(right);
                    ret.push_back(tmp);
                    inserted = true;
                    break;
                }
                else if (newInterval[0] <= intervals[i][1] && newInterval[0] >= intervals[i][0]) 
                {
                    vector<int> tmp{intervals[i][0]};
                    i++;
                    while (i < intervals.size())
                    {
                        if (newInterval[1] >= intervals[i][0]) // 只要左边界重叠就合并
                        {
                            i++;
                        } 
                        else 
                        {
                            break;
                        }
                    }
                        int right = (i > 0) ? max(newInterval[1], intervals[i - 1][1]) : newInterval[1];
                        tmp.push_back(right);
                        ret.push_back(tmp);
                        inserted = true;
                        break; //跳出循环，后续区间直接追加
                } 
                else 
                {
                    // 处理newInterval在当前区间左侧的情况
                    if (newInterval[1] < intervals[i][0]) 
                    {
                        ret.push_back(newInterval);
                        inserted = true;
                        break;
                    }
                    ret.push_back(intervals[i]);
                    i++;
                }
            }
            // 处理newInterval在所有区间右侧或未插入的情况
            if (!inserted) {
                ret.push_back(newInterval);
            }
            // 追加剩余未处理的区间
            while (i < intervals.size()) {
                ret.push_back(intervals[i]);
                i++;
            }
            return ret;
        }
    };